package ljl.codetop300;

import java.util.Arrays;
import java.util.NavigableMap;

/**
 * 人家一题多解，我却一个都想不出来
 */
public class _75_sort_colors {

  /**
   * 思路是两趟双指针，第一趟把 0 就位，第二趟把 1 就位
   */
  static class s1 {
    public void sortColors(int[] nums) {
      int n = nums.length;
      int ptr = 0;
      for (int i = 0; i < n; ++i) {
        if (nums[i] == 0) {
          int temp = nums[i];
          nums[i] = nums[ptr];
          nums[ptr] = temp;
          ++ptr;
        }
      }
      for (int i = ptr; i < n; ++i) {
        if (nums[i] == 1) {
          int temp = nums[i];
          nums[i] = nums[ptr];
          nums[ptr] = temp;
          ++ptr;
        }
      }
    }
  }
  static class s1_good {
    int[] nums;
    public void sortColors(int[] nums) {
      this.nums = nums;
      int p0 = 0;
      for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {
          swap(i, p0++);
        }
      }
      for (int i = p0; i < nums.length; i++) {
        if (nums[i] == 1) {
          swap(i, p0++);
        }
      }
    }
    void swap(int i, int j) {
      int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }

  }

  /**
   * 阴间解法
   */
  static class s2 {
    public void sortColors(int[] nums) {
      int n = nums.length;
      int p0 = 0, p1 = 0;
      for (int i = 0; i < n; ++i) {
        // 221100
        // 112200 - 012210 由于 p0=0 < p1=2 还得交换 p1 和 i，于是 011220，然后 p0 p1 都增加
        // 011220 - 001221 p0=1, p1=2 还是小，还得交换 p1 和 i，于是 001122
        if (nums[i] == 1) {
          int temp = nums[i];
          nums[i] = nums[p1];
          nums[p1] = temp;
          ++p1;
        } else if (nums[i] == 0) {
          int temp = nums[i];
          nums[i] = nums[p0];
          nums[p0] = temp;
          if (p0 < p1) {
            temp = nums[i];
            nums[i] = nums[p1];
            nums[p1] = temp;
          }
          ++p0;
          ++p1;
        }
      }
    }
  }

  static class s2_hell {
    public void sortColors(int[] nums) {
      int p0 = 0;
      int p1 = 0;
      for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 1) {
          swap(nums, i, p1);
          p1++;
        } else if (nums[i] == 0) {
          swap(nums, i, p0);
          // 为什么要和 p1 再次交换，我觉着是这样：现在 p1 在后面，指向一个不为 1 的东西，也就是 2
          // p0 和 i 交换了，肯定是把 1 搞后面了，得再和 p1 指向的 2 交换
          if (p0 < p1) {
            swap(nums, i, p1);
          }
          p0++;
          p1++;
        }
      }
    }
    void swap(int[] nums, int i, int j) {
      if (i != j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
      }
    }
  }

  /**
   * 这个思路和我想的差不多，三指针法属于是
   * 其实也是双指针
   */
  static class s3 {
    public void sortColors(int[] nums) {
      int n = nums.length;
      int p0 = 0, p2 = n - 1;
      for (int i = 0; i <= p2; ++i) {
        while (i <= p2 && nums[i] == 2) {
          int temp = nums[i];
          nums[i] = nums[p2];
          nums[p2] = temp;
          --p2;
        }
        if (nums[i] == 0) {
          int temp = nums[i];
          nums[i] = nums[p0];
          nums[p0] = temp;
          ++p0;
        }
      }
    }
  }

  static class s3_good {
    int[] nums;
    public void sortColors(int[] nums) {
      this.nums = nums;
      int p0 = 0, p2 = nums.length - 1;
      for (int i = 0; i <= p2; i++) {
        if (nums[i] == 2) {
          while (p2 > i && nums[p2] == 2) p2--;
          swap(i, p2--);
        }
        // 这不能是 else，因为上面和 2 交换完可能换过来个 0，如果是这样，还得继续交换
        // 否则就错了
        if (nums[i] == 0) {
          swap(i, p0++);
        }
      }
    }
    void swap(int i, int j) {
      int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }
  }

}
